package offerbook.Code27_BST_Link_Array_Converse;

import offerbook.Code06_ReConstructBT_二叉树重建;
import offerbook.Code24_VerifySequenceOfBST;
import utils.TreeNode;
import utils.TreeUtil;

/**
 * 把一个有序数组转为高度平衡的BST。本题中，
 * 一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
 * <p>
 * 分析：左右两个子树高度差不超过1，其实就是根节点在数组的中间位置。左侧在左子树，右侧在右子树
 * 其实就是二分查找，递归遍历即可。这里的当偶数的时候是第一个也行，是第二个也行，都是BST。
 * <p>
 * 设数组[start,....,end]  第一个偶数  (start + end) >> 1 ...... (length-1) >> 1
 * 或者是 start + (end - start)/2  注意当end-start = -1,用 >> 1会溢出，而用/2不会
 * 设数组[start,....,end]  第二个偶数  (start + end + 1) >> 1 ...... (length) >>1
 * <p>
 * <p>
 * <p>
 * 深入理解BST以及树的遍历，见
 * {@link Code24_VerifySequenceOfBST}
 * {@link Code06_ReConstructBT_二叉树重建}
 * 给定一个后续遍历的数组问是否可能是BST
 */

public class Code27_ConvertArrayToBST {


    public static TreeNode reconstructBST(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return doReconstructBST(arr, 0, arr.length - 1);
    }

    private static TreeNode doReconstructBST(int[] arr, int start, int end) {
        //当start = end，调用递归也一样。
        /*if (start >= end) {
            return start == end? new TreeNode(arr[start]) :null;
        }*/
        if (start > end) {
            return null;
        }
//        int mid = (end + start) >> 1; //如果是偶数则是第一个偶数位
        int mid = (end + start+1) >> 1; //如果是偶数则是第二个偶数位
        TreeNode treeNode = new TreeNode(arr[mid]);
        treeNode.left = doReconstructBST(arr, start, mid - 1);
        treeNode.right = doReconstructBST(arr, mid + 1, end);
        return treeNode;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5, 7, 8, 10};
        int[] arr1 = {-10, -3, 0, 5, 9};

        TreeNode treeNode = reconstructBST(arr);
        TreeNode treeNode1 = reconstructBST(arr1);
        TreeUtil.printTree(treeNode);
        TreeUtil.printTree(treeNode1);
    }
}
